package com.czk.algorithm.prime;

import java.util.Arrays;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/8/2 22:12
 */
public class PrimeAlgorithm {
    public static void main(String[] args) {
        // 顶点数
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        // 个数
        int verx = data.length;
        // 10000这个大数表示两个点不连通
        int[][] weight = {{10000, 5, 7, 10000, 10000, 10000, 2}, {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000}, {10000, 9, 10000, 10000, 100000, 4, 10000},
                {10000, 10000, 10000, 8, 10000, 10000, 5, 4}, {10000, 10000, 1000, 4, 5, 10000, 6}, {2, 3, 10000, 10000, 4, 5, 10000}};
        MRGraph graph = new MRGraph(verx);
        // 创建最小生成树
        MiniTree miniTree = new MiniTree();
        miniTree.createGraph(graph, verx, data, weight);
        // 输出
        miniTree.showGraph(graph);
        miniTree.prime(graph,0);
    }
}

class MiniTree {
    // 创建邻接矩阵

    /**
     * @param graph
     * @param verx
     * @param data
     * @param weight
     */
    public void createGraph(MRGraph graph, int verx, char[] data, int[][] weight) {
        int i;
        for (i = 0; i < verx; i++) {
            graph.data[i] = data[i];
            for (int k = 0; k < verx; k++) {
                graph.weight[i][k] = weight[i][k];
            }
        }
    }

    // 显示图
    public void showGraph(MRGraph graph) {
        for (int[] ints : graph.weight) {
            System.out.println(Arrays.toString(ints));
        }
    }
    // 生成miniTree
    public void prime(MRGraph graph,int v){
        // 标记顶点是否被访问过，默认元素都是0，表示没有被访问过
        int[] visited=new int[graph.verx];
        for (int i = 0; i < graph.verx; i++) {
            visited[i]=0;
        }
        // 把当前节点标记为已访问
        visited[v]=1;
        // 用h1和h2记录两个顶点的坐标
        int h1=-1;
        int h2=-1;
        // 将miniWeight初始为大数
        int miniWeight=10000;
        // verx个节点会生成verx-1条边
        for (int k = 1; k <graph.verx ; k++) {
            // 遍历每次生成的子图，和哪个节点最近
            for (int i = 0; i <graph.verx ; i++) {
                for (int j = 0; j <graph.verx ; j++) {
                    if (visited[i]==1&&visited[j]==0&&graph.weight[i][j]<miniWeight){
                        miniWeight=graph.weight[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }
            // 将找到的顶点设置为已访问
            visited[h2]=1;

            System.out.println("找到第一个顶点"+graph.data[h1]+"第二个顶点"+graph.data[h2]+"权值是"+miniWeight);
            // 重置最大值
            miniWeight=10000;
        }
    }
}

// 创建图
class MRGraph {
    // 顶点个数
    int verx;
    // 节点数据
    char[] data;
    // 邻接矩阵
    int[][] weight;

    public MRGraph(int verx) {
        this.verx = verx;
        data = new char[verx];
        weight = new int[verx][verx];
    }

}
